package com.singzi.leetcode.N800;

public class T0748 {
    public static void main(String[] args) {
        String licensePlate =  "Ah71752";
        Solution0748 solution0748 = new Solution0748();
        String[] words = {"suggest","letter","of","husband","easy","education","drug","prevent","writer","old"};
        System.out.println(solution0748.shortestCompletingWord(licensePlate, words));
    }


}
class Solution0748 {
    public String shortestCompletingWord(String licensePlate, String[] words) {

        int min  = 99;
        int temp;
        int index = 0;
        for(int i = 0;i < words.length; i++){
            temp = verifyWord(licensePlate, words[i]);
            if(temp < min){
                min = temp;
                index = i;
            };
        }
        return words[index];



    }

    public int verifyWord(String licensePlate, String word){

        int index;
        int []letter = new int[26];
        for (int i = 0; i < word.length(); i++) {
            index = ((int)word.charAt(i)-65)%32;
            if(index<0||index>25) continue;
            letter[index] ++;
        }
        for (int i = 0; i < licensePlate.length(); i++) {
            index = ((int)licensePlate.charAt(i)-65)%32;
            if(index<0||index>25) continue;
            letter[index] --;
            if(letter[index]<0) return 999;
        }




        return word.length();

    }
}